package ch3.part2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的前序、中序、后序、层序遍历
 * 层序打印使用Queue队列实现，前中后序打印可使用Stack栈来实现
 *
 * @author liuwanxiang
 * @version 2019/05/16
 */
public class BinaryTreeTraversal {

    /**
     * 前序打印，根左右
     *
     * @param node
     */
    private static void prePrint(BinaryTreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        prePrint(node.leftChild);
        prePrint(node.rightChild);
    }

    /**
     * 中序打印，左根右
     *
     * @param node
     */
    private static void midPrint(BinaryTreeNode node) {
        if (node == null) {
            return;
        }
        if (node.leftChild != null) {
            midPrint(node.leftChild);
        }
        System.out.print(node.data + " ");
        if (node.rightChild != null) {
            midPrint(node.rightChild);
        }
    }

    /**
     * 后序打印，左右根
     *
     * @param node
     */
    private static void behindPrint(BinaryTreeNode node) {
        if (node == null) {
            return;
        }
        if (node.leftChild != null) {
            behindPrint(node.leftChild);
        }
        if (node.rightChild != null) {
            behindPrint(node.rightChild);
        }
        System.out.print(node.data + " ");
    }

    /**
     * 层序打印
     *
     * @param node
     */
    private static void seqPrint(BinaryTreeNode node) {
        LinkedList<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(node);
        BinaryTreeNode temp;
        while (!queue.isEmpty()) {
            temp = queue.poll();
            System.out.print(temp.data + " ");
            if (temp.leftChild != null) {
                queue.offer(temp.leftChild);
            }
            if (temp.rightChild != null) {
                queue.offer(temp.rightChild);
            }
        }
    }

    /**
     * 基于栈数据结构的二叉树前序遍历
     * 步骤分析：
     * | n| print|stack-oper| next|stack
     * | 1|     3| push 8   |    2|8
     * | 2|     2| push 10  |    9|8 10
     * | 3|     9| push null| null|8 10 null
     * | 4|     -|  pop null| null|8 10
     * | 5|     -|  pop 10  |   10|8
     * | 6|    10| push null| null|8 null
     * | 7|     -|  pop null| null|8
     * | 8|     -|  pop 8   |    8|
     * | 9|     8| push 4   | null|4
     * |10|     -|  pop 4   |    4|
     * |11|     4| push null| null|null
     * |12|     -|  pop null| null|
     *
     * @param rootNode
     */
    private static void prePrintStack(BinaryTreeNode rootNode) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode treeNode = rootNode;
        while (treeNode != null || !stack.isEmpty()) {
            while (treeNode != null) {
                System.out.print(treeNode + " ");
                stack.push(treeNode.rightChild);
                treeNode = treeNode.leftChild;
            }
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
            }
        }
    }

    /**
     * 基于栈数据结构的二叉树中序遍历
     *
     * @param rootNode
     */
    private static void midPrintStack(BinaryTreeNode rootNode) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode node = rootNode;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                if (node != null) {
                    System.out.print(node + " ");
                    node = node.rightChild;
                }
            }
        }
    }

    /**
     * 使用中间堆栈存放过程数据，似懂非懂
     * 基于栈数据结构的二叉树后序遍历
     * <p>
     * Note:
     * 2019-5-17 本程序的思路：
     * 前序遍历为根左右，后序遍历为左右根。
     * 既然左右根不好进行遍历，那就使用根右做来进行遍历，之后再进行倒序输出。
     *
     * @param rootNode
     */
    private static void behindPrintStack(BinaryTreeNode rootNode) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        Stack<BinaryTreeNode> output = new Stack<>();
        BinaryTreeNode node = rootNode;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                output.push(node);
                node = node.rightChild;
            } else {
                node = stack.pop();
                node = node.leftChild;
            }
        }
        while (!output.isEmpty()) {
            System.out.print(output.pop() + " ");
        }
    }

    public static void main(String[] args) {

        // 3 2 9 null null 10 null null 8 null 4
        // List<Integer> treeList = new ArrayList<>(Arrays.asList(3, 2, 9, null, null, 10, null, null, 8, null, 4));

        // 1 2 4 null null 5 null null 3 6 null null 7 null null
        List<Integer> treeList = new ArrayList<>(Arrays.asList(1, 2, 4, null, null, 5, null, null, 3, 6, null, null, 7));
        BinaryTreeNode binaryTree = BinaryTreeNode.createBinaryTree(treeList);
        // 构建出来的二叉树
        //        3
        //    2      8
        //  9 10  null 4

        // 前序遍历打印 根左右 3 2 9 10 8 4
        System.out.print("前序遍历: ");
        prePrint(binaryTree);

        System.out.print("\n-----------------\n");

        // 中序遍历打印 左根右 9 2 10 3 8 4
        System.out.print("中序遍历: ");
        midPrint(binaryTree);

        System.out.print("\n-----------------\n");

        // 后序遍历打印 左右根 9 10 2 4 8 3
        System.out.print("后序遍历: ");
        behindPrint(binaryTree);

        System.out.print("\n-----------------\n");

        // 层序遍历打印 分层打 3 2 8 9 10 4
        System.out.print("层序遍历: ");
        seqPrint(binaryTree);

        System.out.print("\n-----------------\n");

        // 前序遍历打印 根左右 3 2 9 10 8 4
        System.out.print("前序遍历: ");
        prePrintStack(binaryTree);

        System.out.print("\n-----------------\n");

        // 中序遍历打印 左根右 9 2 10 3 8 4
        System.out.print("中序遍历: ");
        midPrintStack(binaryTree);

        System.out.print("\n-----------------\n");

        // 后序遍历打印 左右根 9 10 2 4 8 3
        System.out.print("后序遍历: ");
        behindPrintStack(binaryTree);

    }

}
